#include <vector>

using namespace std;

class Solution {
public:

    //leetcode: 283. 移动零
    // https://leetcode.cn/problems/move-zeroes/
    //法一：数组存储
    // void moveZeroes(vector<int>& nums) {
    //     vector<int> tmp;
    //     tmp.reserve(nums.size());
    //     int zero_num = 0;
    //     for (auto num : nums)
    //     {
    //         if (num == 0)
    //         {
    //             ++zero_num;
    //         }
    //         else 
    //         {
    //             tmp.push_back(num);
    //         }
    //     }
    //     while (zero_num)
    //     {
    //         tmp.push_back(0);
    //         --zero_num;
    //     }
    //     nums.swap(tmp);
    // }
    //法二：双指针
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        while (cur < nums.size())
        {
            if (nums[cur])
            {
                ++dest;
                swap(nums[dest], nums[cur]);
            }
            ++cur;
        }
    }


    //////////////////////////////////////////////////////////////
    //leetcode: 1089. 复写零
    // https://leetcode.cn/problems/duplicate-zeros/
    //法一：数组存储+双指针
    // void duplicateZeros(vector<int>& arr) {
    //     int fast = 0;
    //     int last = 0;
    //     vector<int> nums;
    //     nums.resize(arr.size());
    //     while (fast < arr.size())
    //     {
    //         if (arr[last] == 0)
    //         {
    //             nums[fast++] = arr[last];
    //         }
    //         if (fast < arr.size())
    //             nums[fast] = arr[last];
    //         ++last;
    //         ++fast;
    //     }
    //     arr.swap(nums);
    // }
    //法二：双指针（法一优化）
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int size = arr.size();

        while (cur < size)
        {
            if (arr[cur])
                dest++;
            else
                dest += 2;
            if (dest >= size -1)
                break;
            ++cur;
        }

        if (dest == size)
        {
            arr[size-1] = 0;
            dest -= 2;
            cur--;
        }

        while (cur >= 0)
        {
            arr[dest] = arr[cur];
            if (arr[cur] == 0)
            {
                arr[--dest] = arr[cur];
            }
            --dest;
            --cur;
        }
    }

    //////////////////////////////////////////
    //leetcode: 202. 快乐数
    // https://leetcode.cn/problems/happy-number/
    int getNum(int num)
    {
        int ret = 0;
        while (num)
        {
            ret += ((num%10)*(num%10));
            num /= 10;
        }
        return ret;
    }

    bool isHappy(int n) {
        int fast = getNum(n);
        int slow = n;
        while (fast != slow)
        {
            slow = getNum(slow);
            fast = getNum(getNum(fast));
        }
        if (fast == 1)
            return true;
        else
            return false;
    }

};